package cn.genmer.test.security.algorithm.program;

import com.alibaba.fastjson.JSONObject;

/**
 * 字符串匹配算法（多模式串） Trie树
 * 原方法，有空格会有问题 - 解决了
 * 问题是，这匹配根本没用吧
 * https://blog.csdn.net/mingyunxiaohai/article/details/87898250
 */
public class Trie {
    private TrieNode root = new TrieNode('/'); // 存储无意义字符

    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("atqaextisgoodgood".toCharArray());
        System.out.println(trie.find("aex".toCharArray()));
    }

    // 往 Trie 树中插入一个字符串
    public void insert(char[] text) {
        TrieNode p = root;
        System.out.println(String.format("插入前数组情况：", JSONObject.parseObject(JSONObject.toJSONString(p))));
        for (int i = 0; i < text.length; ++i) {
            int index = text[i] - 'a';
            if (index < 0) index = 26;
            if (p.children[index] == null) {
                TrieNode newNode = new TrieNode(text[i]);
                p.children[index] = newNode;
            }
            p = p.children[index];
        }
        p.isEndingChar = true;
        System.out.println(String.format("插入后数组情况：", JSONObject.parseObject(JSONObject.toJSONString(p))));
        System.out.println(String.format("数组第一个值：%s", p.children[0]));
    }

    // 在 Trie 树中查找一个字符串
    public boolean find(char[] pattern) {
        TrieNode p = root;
        for (int i = 0; i < pattern.length; ++i) {
            int index = pattern[i] - 'a';
            if (p.children[index] == null) {
                return false; // 不存在 pattern
            }
            System.out.println("查找到的: " + p.children[index].data);
            p = p.children[index];
        }
        if (p.isEndingChar == false) return false; // 不能完全匹配，只是前缀
        else return true; // 找到 pattern
    }

    public class TrieNode {
        public char data;
        public TrieNode[] children = new TrieNode[27];
        public boolean isEndingChar = false;

        public TrieNode(char data) {
            this.data = data;
        }
    }


}

